#include "Star1p.h"
#include <cfloat>
#include "CommonApps.h"


void Star1p::init(const SenetPlayerExt* owner , int gameStickNum)
{
	m_gameStickNum = gameStickNum;
	m_gameTwoThirdStickNum = ((2*gameStickNum)/3);
	m_probabilities.init(gameStickNum);
	m_heuristic.init(owner , m_probabilities); 
//	m_IsReorderChanceNodes = true;
//	m_IsReorderMinMaxNodes = true;

	// order sticks in m_OrderedChanceNodes
	vector<CommonApps::MoveHeuristicValue> chanceSorter(m_gameStickNum + 1);
	for (int i = 0; i <= m_gameStickNum; ++i)
	{
		CommonApps::MoveHeuristicValue mhv;
		mhv.heuristicScore = m_probabilities.getProbability(i);
		mhv.move = i;
		chanceSorter[i] = mhv;
	}
	CommonApps::MoveHeuristicValue::SortAscMoveHeuristicVector(chanceSorter);
	m_OrderedChanceNodes.resize(m_gameStickNum + 1);
	m_UnOrderedChanceNodes.resize(m_gameStickNum + 1);
	for (int i = 0; i <= m_gameStickNum; ++i)
	{
		m_OrderedChanceNodes[i] = chanceSorter[i].move;
		m_UnOrderedChanceNodes[i] = i;
	}
}

void Star1p::reorderMinMaxNodes(SenetBoardDraft& board,
								vector<int>& moves,
								int stickNum,
								Definitions::PlayerColor currentPlayer,
								NodeType type
								)
{
	// reordering according to heuristic function

	// phase 1: score each move in the moves vector
	int movesSize = moves.size();
	static std::vector<CommonApps::MoveHeuristicValue> movesHvaluesVector;
	static CommonApps::MoveHeuristicValue movesHv[10];
	movesHvaluesVector.clear();
	movesHvaluesVector.resize(movesSize);
	for (int i = 0; i < movesSize; ++i)
	{
		CommonApps::MoveHeuristicValue& mhv = movesHv[i];
		
		int startLoc = moves[i];
		int endLoc = startLoc + stickNum;

		// do move
		static vector<SenetBoardDraftMove> movesPerformed;
		movesPerformed.clear();
		board.doMove(movesPerformed, startLoc, endLoc, currentPlayer);

		// score move
		mhv.heuristicScore = m_heuristic.scoreMini(board);
		mhv.move = startLoc;	

		// undo move
		CommonApps::undoMoves(movesPerformed, board , currentPlayer);

		// save mhv to mhv-vector
		movesHvaluesVector[i] = mhv;
	}

	// phase 2: sort the mhv-vector according to heuristic score
	CommonApps::MoveHeuristicValue::SortAscMoveHeuristicVector(movesHvaluesVector);

	// phase 3: save the moves in the moves vector according to the order
	for (int i = 0; i < movesSize; ++i)
	{
		moves[i] = movesHvaluesVector[i].move;
	}
	int x;
	x = 10;
}

void Star1p::alphabeta(
					  Score& res ,
					  SenetBoardDraft& board,
					  int depth,
					  const GameTimer& timer,
					  bool checkTime,
					  Definitions::PlayerColor currentPlayer,
					  int stickNum /* the number of sticks that current player got */,
					  NodeType nodeType,
					  float alpha,
					  float beta,
					  bool probe)
{
	if(checkTime && timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
	{
		throw Exception::TIME_OUT;
	}
	if(board.isTerminal() || depth == 0)
	{
		res.pieceToMove = -1;
		res.score = m_heuristic.score(board);
		return;
	}

	vector<int> moves;
	board.generateMoves(moves, currentPlayer, stickNum);
	int movesSize = moves.size();
	
	if(movesSize == 0)
	{
		//TODO: consider to continue the search to collect data for next runs
		res.pieceToMove = -1;
		res.score = m_heuristic.score(board);
		return;
	}

	//there are moves to check
	if (m_IsReorderMinMaxNodes)
	{
		reorderMinMaxNodes(board, moves, stickNum, currentPlayer, nodeType);
	}

	Definitions::PlayerColor nextPlayer;
	NodeType nextNodeType;
	if(stickNum == m_gameTwoThirdStickNum || stickNum == 1 || stickNum == m_gameStickNum)
	{
		//next turn I play again
		nextPlayer = currentPlayer;
		nextNodeType = nodeType;
	}
	else
	{
		//next turn my opponent plays
		nextPlayer = Definitions::getOppositePlayer(currentPlayer);
		nextNodeType = CommonApps::getOppositeNodeType(nodeType);
	}

	int startLoc;
	int endLoc;
	float best = 0;
	int pieceToMove = -1;
	if(nodeType == MAX)
	{
		best = -FLT_MAX;
		for(int i = 0 ;	i < movesSize ; ++i)
		{
			startLoc = moves[i];
			endLoc = startLoc + stickNum;

			//do move
			vector<SenetBoardDraftMove> movesPerformed;
			board.doMove(movesPerformed, startLoc, endLoc, currentPlayer);

			//score move
			Score val = chanceSearch(
				board , depth-1 ,
				timer, checkTime ,
				nextPlayer,
				-1 , CHANCE, nextNodeType,
				alpha, beta);
			
			//undo move
			CommonApps::undoMoves(movesPerformed, board , currentPlayer);

			// update the current maximum score
			// the following is actually: current_max = max(current_max, val)
			if(val.score > best)
			{
				best = val.score;
				pieceToMove = startLoc;
			}

			// the following is actually: alpha = max(alpha, best == curmax)
			if (alpha < best)
			{
				alpha = best;
			}

			// the following is the alpha cut-off
			if (best >= beta)
			{
				break;
			}
		}
	}
	else if(nodeType == MIN)
	{
		best = FLT_MAX;
		for(int i = 0; i < movesSize; ++i)
		{
			startLoc = moves[i];
			endLoc = startLoc + stickNum;

			//do move
			vector<SenetBoardDraftMove> movesPerformed;
			board.doMove(movesPerformed, startLoc, endLoc, currentPlayer);

			//score move
			Score val = chanceSearch(
				board, depth-1, timer, checkTime,
				nextPlayer,
				-1, CHANCE, nextNodeType, alpha, beta);

			//undo moves
			CommonApps::undoMoves(movesPerformed, board , currentPlayer);

			// update the current minimum score
			// the following is actually: current_min = min(current_min, val)
			if(val.score < best)
			{
				best = val.score;
				pieceToMove = startLoc;
			}

			// the following is actually: beta = min(beta, best == curmin)
			if (beta > best)
			{
				beta = best;
			}

			// the following is the beta cut-off
			if (best <= alpha)
			{
				break;
			}
		}
	}

	res.score = best;
	res.pieceToMove = pieceToMove;
}

//calculate value at chance nodes
void Star1p::star1p(Score& res,
						 SenetBoardDraft &board,
						 int depth,
						 const GameTimer& timer,
						 bool checkTime, 
						 Definitions::PlayerColor nextPlayer,
						 NodeType nextTurn,
						 float alpha,
						 float beta) throw (Exception)
{
	// checks if time elapsed
	if(checkTime && timer.isMoveTimePassed(GameTimer::NO_OVERHEAD))
	{
		throw Exception::TIME_OUT;
	}

	// checks if we reached a leaf
	if(board.isTerminal() || depth == 0)
	{
		res.pieceToMove = -1;
		res.score = m_heuristic.score(board);
	}
	else
	{
		//more resources to use - continue search
		star1pImpl(res, board, depth, timer, checkTime, nextPlayer, nextTurn, alpha, beta);
	}	
}

void Star1p::reorderChanceNodes(vector<int>& outSticksVector)
{
	outSticksVector[0] = 2;
	outSticksVector[1] = 3;
	outSticksVector[2] = 1;
	outSticksVector[3] = 0;
	outSticksVector[4] = 4;
}

void Star1p::star1pImpl(	Score& res,
							SenetBoardDraft &board,
							int depth,
							const GameTimer& timer,
							bool checkTime, 
							Definitions::PlayerColor nextPlayer,
							NodeType nextTurn,
							float alpha,
							float beta) throw (Exception)
{
	// chance node: no piece is selected here
	res.pieceToMove = -1;

	// get L and U
	float L = m_heuristic.getLowerHeuristicBound();
	float U = m_heuristic.getUpperHeuristicBound();

	// init Yi,Xi
	float Yi = 1.0f; // this is Y0
	float Xi = 0.0f; // this is X1
	float vsum = 0.0f;

	// Star1 search phase
	// for-each chance successor
	const vector<int>& sticksVector = (m_IsReorderChanceNodes ? m_OrderedChanceNodes : m_UnOrderedChanceNodes);
	for(int j = 0; j <= m_gameStickNum; ++j)
	{
		int i /* currentStick */ = sticksVector[j];
		Yi = Yi - m_probabilities.getProbability(i);	// this is Yi+1

		float Ai = ((alpha - U*Yi - Xi) / m_probabilities.getProbability(i));
		float Bi = ((beta - L*Yi - Xi) / m_probabilities.getProbability(i));
		float Ax = CommonApps::floatMax(Ai, L);
		float Bx = CommonApps::floatMin(Bi, U);

		Score val = chanceSearch(
			board, depth-1, timer,
			checkTime, nextPlayer, i,
			nextTurn, DONT_CARE, Ax, Bx);
		vsum += (val.score * m_probabilities.getProbability(i));

		// check fail-soft
		if (val.score <= Ai)
		{
			vsum += (U * Yi);
			res.score = vsum;
			return;
		}
		if (val.score >= Bi)
		{
			vsum += (L * Yi);
			res.score = vsum;
			return;
		}

		// continue to next iteration
		Xi = Xi + m_probabilities.getProbability(i) * val.score;	// this is Xi+1

	}
	res.score = vsum;
}

Score Star1p::chanceSearch(SenetBoardDraft& board,
							int depth,
							const GameTimer& timer,
							bool checkTime,
							Definitions::PlayerColor currentPlayer,
							int stickNum,
							NodeType nodeType,
							NodeType nextTurn,
							float alpha,
							float beta) throw(Exception)
{	
	Score res;
	if(nodeType == CHANCE)
	{
		star1p(res , board, depth, timer, checkTime, currentPlayer, nextTurn, alpha, beta);
	}
	else
	{
		alphabeta(res , board, depth, timer, checkTime, currentPlayer, stickNum , nodeType, alpha, beta, false);
	}
	return res;

}

//main function - init turn parameters and calculation
SenetMove Star1p::scoreStar1p(SenetBoardDraft& board,
								int depth,
								const GameTimer& timer,
								bool checkTime,
								Definitions::PlayerColor myColor,
								int stickNum) throw(Exception)
{	
	if(stickNum == 0)
	{
		//TODO: see that star1 and improvements do the same for empty move
		SenetMove resMove(-1);	
		return resMove;
	}
	
	//calculate score
	Score  res =  chanceSearch(
		board, depth, timer, checkTime,
		myColor, stickNum, MAX , DONT_CARE, -FLT_MAX, FLT_MAX);

	m_FinalBoardScore = res.score;

	SenetMove resMove(res.pieceToMove);	
	return resMove;

}

